package main

import (
	"go-leetcode/leetcode/utils"
	"math"
)

// 98. 验证二叉搜索树
func main() {
	node := utils.SortedArrayToBST([]int{2, 2, 2})

	bst := isValidBST(node)

	println(bst)

}

func isValidBST(root *utils.TreeNode) bool {
	// 直接递归呢
	return helper(root, math.MinInt, math.MaxInt)
}

func helper(root *utils.TreeNode, lower, upper int) bool {
	if root == nil {
		return true
	}

	if root.Val <= lower || root.Val >= upper {
		return false
	}

	return helper(root.Left, lower, root.Val) && helper(root.Right, root.Val, upper)
}

func isValidBST2(root *utils.TreeNode) bool {
	// 前序遍历拿到数组，然后遍历判定是不是升序数组
	arrays := inorderTraversal2(root)

	minValue := math.MinInt

	for _, num := range arrays {
		if num <= minValue {
			return false
		}
		minValue = num
	}
	return true
}

func inorderTraversal2(root *utils.TreeNode) []int {
	var res []int
	if root == nil {
		return nil
	}
	res = append(res, inorderTraversal2(root.Left)...)
	res = append(res, root.Val)
	res = append(res, inorderTraversal2(root.Right)...)
	return res
}

// 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
//
//有效 二叉搜索树定义如下：
//
//节点的左
//子树
//只包含 小于 当前节点的数。
//节点的右子树只包含 大于 当前节点的数。
//所有左子树和右子树自身必须也是二叉搜索树。
//
//示例 1：
//
//输入：root = [2,1,3]
//输出：true
//示例 2：
//
//输入：root = [5,1,4,null,null,3,6]
//输出：false
//解释：根节点的值是 5 ，但是右子节点的值是 4 。
//
//提示：
//
//树中节点数目范围在[1, 104] 内
//-231 <= Node.val <= 231 - 1
